# 分隔链表： https://leetcode-cn.com/problems/partition-list/


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

        
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        """
            把小于x的拿出来，组成一个链表，拼接 剩下大于 x的
        """
        # 增加头结点，统一逻辑
        dumpy = ListNode(0, head)
        newDumpy = ListNode(0)
        tail = newDumpy
        pre = dumpy
        cur = head
        node = None
        while cur:
            if cur.val < x:
                print(pre.val)
                # 拿出节点
                pre.next = pre.next.next
                node = cur
                cur = cur.next
                node.next = None

                # 拼接到新链表尾部
                tail.next = node
                tail = tail.next
            else:
                cur = cur.next
                pre = pre.next

        # 拼接
        tail.next = dumpy.next

        return newDumpy.next    